home *** CD-ROM | disk | FTP | other *** search
/ FishMarket 1.0 / FishMarket v1.0.iso / fishies / 401-425 / disk_407 / flex / src.lzh / src / parse.y < prev    next >
Text File  |  1990-07-14  |  15KB  |  705 lines
  1.  
  2. /* parse.y - parser for flex input */
  3.  
  4. %token CHAR NUMBER SECTEND SCDECL XSCDECL WHITESPACE NAME PREVCCL EOF_OP
  5.  
  6. %{
  7. /*-
  8.  * Copyright (c) 1990 The Regents of the University of California.
  9.  * All rights reserved.
  10.  *
  11.  * This code is derived from software contributed to Berkeley by
  12.  * Vern Paxson.
  13.  * 
  14.  * The United States Government has rights in this work pursuant
  15.  * to contract no. DE-AC03-76SF00098 between the United States
  16.  * Department of Energy and the University of California.
  17.  *
  18.  * Redistribution and use in source and binary forms are permitted provided
  19.  * that: (1) source distributions retain this entire copyright notice and
  20.  * comment, and (2) distributions including binaries display the following
  21.  * acknowledgement:  ``This product includes software developed by the
  22.  * University of California, Berkeley and its contributors'' in the
  23.  * documentation or other materials provided with the distribution and in
  24.  * all advertising materials mentioning features or use of this software.
  25.  * Neither the name of the University nor the names of its contributors may
  26.  * be used to endorse or promote products derived from this software without
  27.  * specific prior written permission.
  28.  * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR IMPLIED
  29.  * WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED WARRANTIES OF
  30.  * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
  31.  */
  32.  
  33. #ifndef lint
  34. static char rcsid[] =
  35.     "@(#) $Header: WPL:Generators/flex-2.3/RCS/parse.y,v 1.2 90/07/15 01:16:53 loftus Exp $ (LBL)";
  36. #endif
  37.  
  38. #include "flexdef.h"
  39.  
  40. int pat, scnum, eps, headcnt, trailcnt, anyccl, lastchar, i, actvp, rulelen;
  41. int trlcontxt, xcluflg, cclsorted, varlength, variable_trail_rule;
  42. Char clower();
  43. void build_eof_action();
  44. void yyerror( char * );
  45.  
  46. static int madeany = false;  /* whether we've made the '.' character class */
  47. int previous_continued_action;    /* whether the previous rule's action was '|' */
  48.  
  49. %}
  50.  
  51. %%
  52. goal            :  initlex sect1 sect1end sect2 initforrule
  53.             { /* add default rule */
  54.             int def_rule;
  55.  
  56.             pat = cclinit();
  57.             cclnegate( pat );
  58.  
  59.             def_rule = mkstate( -pat );
  60.  
  61.             finish_rule( def_rule, false, 0, 0 );
  62.  
  63.             for ( i = 1; i <= lastsc; ++i )
  64.                 scset[i] = mkbranch( scset[i], def_rule );
  65.  
  66.             if ( spprdflt )
  67.                 fputs( "YY_FATAL_ERROR( \"flex scanner jammed\" )",
  68.                    temp_action_file );
  69.             else
  70.                 fputs( "ECHO", temp_action_file );
  71.  
  72.             fputs( ";\n\tYY_BREAK\n", temp_action_file );
  73.             }
  74.         ;
  75.  
  76. initlex         :
  77.             {
  78.             /* initialize for processing rules */
  79.  
  80.             /* create default DFA start condition */
  81.             scinstal( "INITIAL", false );
  82.             }
  83.         ;
  84.  
  85. sect1        :  sect1 startconddecl WHITESPACE namelist1 '\n'
  86.         |
  87.         |  error '\n'
  88.             { synerr( "unknown error processing section 1" ); }
  89.         ;
  90.  
  91. sect1end    :  SECTEND
  92.         ;
  93.  
  94. startconddecl   :  SCDECL
  95.             {
  96.             /* these productions are separate from the s1object
  97.              * rule because the semantics must be done before
  98.              * we parse the remainder of an s1object
  99.              */
  100.  
  101.             xcluflg = false;
  102.             }
  103.  
  104.         |  XSCDECL
  105.             { xcluflg = true; }
  106.         ;
  107.  
  108. namelist1    :  namelist1 WHITESPACE NAME
  109.             { scinstal( nmstr, xcluflg ); }
  110.  
  111.         |  NAME
  112.             { scinstal( nmstr, xcluflg ); }
  113.  
  114.         |  error
  115.                         { synerr( "bad start condition list" ); }
  116.         ;
  117.  
  118. sect2           :  sect2 initforrule flexrule '\n'
  119.         |
  120.         ;
  121.  
  122. initforrule     :
  123.             {
  124.             /* initialize for a parse of one rule */
  125.             trlcontxt = variable_trail_rule = varlength = false;
  126.             trailcnt = headcnt = rulelen = 0;
  127.             current_state_type = STATE_NORMAL;
  128.             previous_continued_action = continued_action;
  129.             new_rule();
  130.             }
  131.         ;
  132.  
  133. flexrule        :  scon '^' rule
  134.                         {
  135.             pat = $3;
  136.             finish_rule( pat, variable_trail_rule,
  137.                      headcnt, trailcnt );
  138.  
  139.             for ( i = 1; i <= actvp; ++i )
  140.                 scbol[actvsc[i]] =
  141.                 mkbranch( scbol[actvsc[i]], pat );
  142.  
  143.             if ( ! bol_needed )
  144.                 {
  145.                 bol_needed = true;
  146.  
  147.                 if ( performance_report )
  148.                 pinpoint_message( 
  149.                 "'^' operator results in sub-optimal performance" );
  150.                 }
  151.             }
  152.  
  153.         |  scon rule
  154.                         {
  155.             pat = $2;
  156.             finish_rule( pat, variable_trail_rule,
  157.                      headcnt, trailcnt );
  158.  
  159.             for ( i = 1; i <= actvp; ++i )
  160.                 scset[actvsc[i]] =
  161.                 mkbranch( scset[actvsc[i]], pat );
  162.             }
  163.  
  164.                 |  '^' rule
  165.             {
  166.             pat = $2;
  167.             finish_rule( pat, variable_trail_rule,
  168.                      headcnt, trailcnt );
  169.  
  170.             /* add to all non-exclusive start conditions,
  171.              * including the default (0) start condition
  172.              */
  173.  
  174.             for ( i = 1; i <= lastsc; ++i )
  175.                 if ( ! scxclu[i] )
  176.                 scbol[i] = mkbranch( scbol[i], pat );
  177.  
  178.             if ( ! bol_needed )
  179.                 {
  180.                 bol_needed = true;
  181.  
  182.                 if ( performance_report )
  183.                 pinpoint_message(
  184.                 "'^' operator results in sub-optimal performance" );
  185.                 }
  186.             }
  187.  
  188.                 |  rule
  189.             {
  190.             pat = $1;
  191.             finish_rule( pat, variable_trail_rule,
  192.                      headcnt, trailcnt );
  193.  
  194.             for ( i = 1; i <= lastsc; ++i )
  195.                 if ( ! scxclu[i] )
  196.                 scset[i] = mkbranch( scset[i], pat );
  197.             }
  198.  
  199.                 |  scon EOF_OP
  200.             { build_eof_action(); }
  201.  
  202.                 |  EOF_OP
  203.             {
  204.             /* this EOF applies to all start conditions
  205.              * which don't already have EOF actions
  206.              */
  207.             actvp = 0;
  208.  
  209.             for ( i = 1; i <= lastsc; ++i )
  210.                 if ( ! sceof[i] )
  211.                 actvsc[++actvp] = i;
  212.  
  213.             if ( actvp == 0 )
  214.                 pinpoint_message(
  215.         "warning - all start conditions already have <<EOF>> rules" );
  216.  
  217.             else
  218.                 build_eof_action();
  219.             }
  220.  
  221.                 |  error
  222.             { synerr( "unrecognized rule" ); }
  223.         ;
  224.  
  225. scon            :  '<' namelist2 '>'
  226.         ;
  227.  
  228. namelist2       :  namelist2 ',' NAME
  229.                         {
  230.             if ( (scnum = sclookup( nmstr )) == 0 )
  231.                 format_pinpoint_message(
  232.                 "undeclared start condition %s", nmstr );
  233.  
  234.             else
  235.                 actvsc[++actvp] = scnum;
  236.             }
  237.  
  238.         |  NAME
  239.             {
  240.             if ( (scnum = sclookup( nmstr )) == 0 )
  241.                 format_pinpoint_message(
  242.                 "undeclared start condition %s", nmstr );
  243.             else
  244.                 actvsc[actvp = 1] = scnum;
  245.             }
  246.  
  247.         |  error
  248.             { synerr( "bad start condition list" ); }
  249.         ;
  250.  
  251. rule            :  re2 re
  252.             {
  253.             if ( transchar[lastst[$2]] != SYM_EPSILON )
  254.                 /* provide final transition \now/ so it
  255.                  * will be marked as a trailing context
  256.                  * state
  257.                  */
  258.                 $2 = link_machines( $2, mkstate( SYM_EPSILON ) );
  259.  
  260.             mark_beginning_as_normal( $2 );
  261.             current_state_type = STATE_NORMAL;
  262.  
  263.             if ( previous_continued_action )
  264.                 {
  265.                 /* we need to treat this as variable trailing
  266.                  * context so that the backup does not happen
  267.                  * in the action but before the action switch
  268.                  * statement.  If the backup happens in the
  269.                  * action, then the rules "falling into" this
  270.                  * one's action will *also* do the backup,
  271.                  * erroneously.
  272.                  */
  273.                 if ( ! varlength || headcnt != 0 )
  274.                 {
  275.                 fprintf( stderr,
  276.     "%s: warning - trailing context rule at line %d made variable because\n",
  277.                      program_name, linenum );
  278.                 fprintf( stderr,
  279.                      "      of preceding '|' action\n" );
  280.                 }
  281.  
  282.                 /* mark as variable */
  283.                 varlength = true;
  284.                 headcnt = 0;
  285.                 }
  286.  
  287.             if ( varlength && headcnt == 0 )
  288.                 { /* variable trailing context rule */
  289.                 /* mark the first part of the rule as the accepting
  290.                  * "head" part of a trailing context rule
  291.                  */
  292.                 /* by the way, we didn't do this at the beginning
  293.                  * of this production because back then
  294.                  * current_state_type was set up for a trail
  295.                  * rule, and add_accept() can create a new
  296.                  * state ...
  297.                  */
  298.                 add_accept( $1, num_rules | YY_TRAILING_HEAD_MASK );
  299.                 variable_trail_rule = true;
  300.                 }
  301.             
  302.             else
  303.                 trailcnt = rulelen;
  304.  
  305.             $$ = link_machines( $1, $2 );
  306.             }
  307.  
  308.         |  re2 re '$'
  309.             { synerr( "trailing context used twice" ); }
  310.  
  311.         |  re '$'
  312.                         {
  313.             if ( trlcontxt )
  314.                 {
  315.                 synerr( "trailing context used twice" );
  316.                 $$ = mkstate( SYM_EPSILON );
  317.                 }
  318.  
  319.             else if ( previous_continued_action )
  320.                 {
  321.                 /* see the comment in the rule for "re2 re"
  322.                  * above
  323.                  */
  324.                 if ( ! varlength || headcnt != 0 )
  325.                 {
  326.                 fprintf( stderr,
  327.     "%s: warning - trailing context rule at line %d made variable because\n",
  328.                      program_name, linenum );
  329.                 fprintf( stderr,
  330.                      "      of preceding '|' action\n" );
  331.                 }
  332.  
  333.                 /* mark as variable */
  334.                 varlength = true;
  335.                 headcnt = 0;
  336.                 }
  337.  
  338.             trlcontxt = true;
  339.  
  340.             if ( ! varlength )
  341.                 headcnt = rulelen;
  342.  
  343.             ++rulelen;
  344.             trailcnt = 1;
  345.  
  346.             eps = mkstate( SYM_EPSILON );
  347.             $$ = link_machines( $1,
  348.                  link_machines( eps, mkstate( '\n' ) ) );
  349.             }
  350.  
  351.         |  re
  352.             {
  353.                 $$ = $1;
  354.  
  355.             if ( trlcontxt )
  356.                 {
  357.                 if ( varlength && headcnt == 0 )
  358.                 /* both head and trail are variable-length */
  359.                 variable_trail_rule = true;
  360.                 else
  361.                 trailcnt = rulelen;
  362.                 }
  363.                 }
  364.         ;
  365.  
  366.  
  367. re              :  re '|' series
  368.                         {
  369.             varlength = true;
  370.             $$ = mkor( $1, $3 );
  371.             }
  372.  
  373.         |  series
  374.             { $$ = $1; }
  375.         ;
  376.  
  377.  
  378. re2        :  re '/'
  379.             {
  380.             /* this rule is written separately so
  381.              * the reduction will occur before the trailing
  382.              * series is parsed
  383.              */
  384.  
  385.             if ( trlcontxt )
  386.                 synerr( "trailing context used twice" );
  387.             else
  388.                 trlcontxt = true;
  389.  
  390.             if ( varlength )
  391.                 /* we hope the trailing context is fixed-length */
  392.                 varlength = false;
  393.             else
  394.                 headcnt = rulelen;
  395.  
  396.             rulelen = 0;
  397.  
  398.             current_state_type = STATE_TRAILING_CONTEXT;
  399.             $$ = $1;
  400.             }
  401.         ;
  402.  
  403. series          :  series singleton
  404.                         {
  405.             /* this is where concatenation of adjacent patterns
  406.              * gets done
  407.              */
  408.             $$ = link_machines( $1, $2 );
  409.             }
  410.  
  411.         |  singleton
  412.             { $$ = $1; }
  413.         ;
  414.  
  415. singleton       :  singleton '*'
  416.                         {
  417.             varlength = true;
  418.  
  419.             $$ = mkclos( $1 );
  420.             }
  421.  
  422.         |  singleton '+'
  423.             {
  424.             varlength = true;
  425.  
  426.             $$ = mkposcl( $1 );
  427.             }
  428.  
  429.         |  singleton '?'
  430.             {
  431.             varlength = true;
  432.  
  433.             $$ = mkopt( $1 );
  434.             }
  435.  
  436.         |  singleton '{' NUMBER ',' NUMBER '}'
  437.             {
  438.             varlength = true;
  439.  
  440.             if ( $3 > $5 || $3 < 0 )
  441.                 {
  442.                 synerr( "bad iteration values" );
  443.                 $$ = $1;
  444.                 }
  445.             else
  446.                 {
  447.                 if ( $3 == 0 )
  448.                 $$ = mkopt( mkrep( $1, $3, $5 ) );
  449.                 else
  450.                 $$ = mkrep( $1, $3, $5 );
  451.                 }
  452.             }
  453.  
  454.         |  singleton '{' NUMBER ',' '}'
  455.             {
  456.             varlength = true;
  457.  
  458.             if ( $3 <= 0 )
  459.                 {
  460.                 synerr( "iteration value must be positive" );
  461.                 $$ = $1;
  462.                 }
  463.  
  464.             else
  465.                 $$ = mkrep( $1, $3, INFINITY );
  466.             }
  467.  
  468.         |  singleton '{' NUMBER '}'
  469.             {
  470.             /* the singleton could be something like "(foo)",
  471.              * in which case we have no idea what its length
  472.              * is, so we punt here.
  473.              */
  474.             varlength = true;
  475.  
  476.             if ( $3 <= 0 )
  477.                 {
  478.                 synerr( "iteration value must be positive" );
  479.                 $$ = $1;
  480.                 }
  481.  
  482.             else
  483.                 $$ = link_machines( $1, copysingl( $1, $3 - 1 ) );
  484.             }
  485.  
  486.         |  '.'
  487.             {
  488.             if ( ! madeany )
  489.                 {
  490.                 /* create the '.' character class */
  491.                 anyccl = cclinit();
  492.                 ccladd( anyccl, '\n' );
  493.                 cclnegate( anyccl );
  494.  
  495.                 if ( useecs )
  496.                 mkeccl( ccltbl + cclmap[anyccl],
  497.                     ccllen[anyccl], nextecm,
  498.                     ecgroup, csize, csize );
  499.  
  500.                 madeany = true;
  501.                 }
  502.  
  503.             ++rulelen;
  504.  
  505.             $$ = mkstate( -anyccl );
  506.             }
  507.  
  508.         |  fullccl
  509.             {
  510.             if ( ! cclsorted )
  511.                 /* sort characters for fast searching.  We use a
  512.                  * shell sort since this list could be large.
  513.                  */
  514.                 cshell( ccltbl + cclmap[$1], ccllen[$1], true );
  515.  
  516.             if ( useecs )
  517.                 mkeccl( ccltbl + cclmap[$1], ccllen[$1],
  518.                     nextecm, ecgroup, csize, csize );
  519.  
  520.             ++rulelen;
  521.  
  522.             $$ = mkstate( -$1 );
  523.             }
  524.  
  525.         |  PREVCCL
  526.             {
  527.             ++rulelen;
  528.  
  529.             $$ = mkstate( -$1 );
  530.             }
  531.  
  532.         |  '"' string '"'
  533.             { $$ = $2; }
  534.  
  535.         |  '(' re ')'
  536.             { $$ = $2; }
  537.  
  538.         |  CHAR
  539.             {
  540.             ++rulelen;
  541.  
  542.             if ( caseins && $1 >= 'A' && $1 <= 'Z' )
  543.                 $1 = clower( $1 );
  544.  
  545.             $$ = mkstate( $1 );
  546.             }
  547.         ;
  548.  
  549. fullccl        :  '[' ccl ']'
  550.             { $$ = $2; }
  551.  
  552.         |  '[' '^' ccl ']'
  553.             {
  554.             /* *Sigh* - to be compatible Unix lex, negated ccls
  555.              * match newlines
  556.              */
  557. #ifdef NOTDEF
  558.             ccladd( $3, '\n' ); /* negated ccls don't match '\n' */
  559.             cclsorted = false; /* because we added the newline */
  560. #endif
  561.             cclnegate( $3 );
  562.             $$ = $3;
  563.             }
  564.         ;
  565.  
  566. ccl             :  ccl CHAR '-' CHAR
  567.                         {
  568.             if ( $2 > $4 )
  569.                 synerr( "negative range in character class" );
  570.  
  571.             else
  572.                 {
  573.                 if ( caseins )
  574.                 {
  575.                 if ( $2 >= 'A' && $2 <= 'Z' )
  576.                     $2 = clower( $2 );
  577.                 if ( $4 >= 'A' && $4 <= 'Z' )
  578.                     $4 = clower( $4 );
  579.                 }
  580.  
  581.                 for ( i = $2; i <= $4; ++i )
  582.                     ccladd( $1, i );
  583.  
  584.                 /* keep track if this ccl is staying in alphabetical
  585.                  * order
  586.                  */
  587.                 cclsorted = cclsorted && ($2 > lastchar);
  588.                 lastchar = $4;
  589.                 }
  590.  
  591.             $$ = $1;
  592.             }
  593.  
  594.         |  ccl CHAR
  595.                 {
  596.             if ( caseins )
  597.                 if ( $2 >= 'A' && $2 <= 'Z' )
  598.                 $2 = clower( $2 );
  599.  
  600.             ccladd( $1, $2 );
  601.             cclsorted = cclsorted && ($2 > lastchar);
  602.             lastchar = $2;
  603.             $$ = $1;
  604.             }
  605.  
  606.         |
  607.             {
  608.             cclsorted = true;
  609.             lastchar = 0;
  610.             $$ = cclinit();
  611.             }
  612.         ;
  613.  
  614. string        :  string CHAR
  615.                         {
  616.             if ( caseins )
  617.                 if ( $2 >= 'A' && $2 <= 'Z' )
  618.                 $2 = clower( $2 );
  619.  
  620.             ++rulelen;
  621.  
  622.             $$ = link_machines( $1, mkstate( $2 ) );
  623.             }
  624.  
  625.         |
  626.             { $$ = mkstate( SYM_EPSILON ); }
  627.         ;
  628.  
  629. %%
  630.  
  631.  
  632. /* build_eof_action - build the "<<EOF>>" action for the active start
  633.  *                    conditions
  634.  */
  635.  
  636. void build_eof_action()
  637.  
  638.     {
  639.     register int i;
  640.  
  641.     for ( i = 1; i <= actvp; ++i )
  642.     {
  643.     if ( sceof[actvsc[i]] )
  644.         format_pinpoint_message(
  645.         "multiple <<EOF>> rules for start condition %s",
  646.             scname[actvsc[i]] );
  647.  
  648.     else
  649.         {
  650.         sceof[actvsc[i]] = true;
  651.         fprintf( temp_action_file, "case YY_STATE_EOF(%s):\n",
  652.              scname[actvsc[i]] );
  653.         }
  654.     }
  655.  
  656.     line_directive_out( temp_action_file );
  657.     }
  658.  
  659.  
  660. /* synerr - report a syntax error */
  661.  
  662. void synerr( str )
  663. char str[];
  664.  
  665.     {
  666.     syntaxerror = true;
  667.     pinpoint_message( str );
  668.     }
  669.  
  670.  
  671. /* format_pinpoint_message - write out a message formatted with one string,
  672.  *                 pinpointing its location
  673.  */
  674.  
  675. void format_pinpoint_message( msg, arg )
  676. char msg[], arg[];
  677.  
  678.     {
  679.     char errmsg[MAXLINE];
  680.  
  681.     (void) sprintf( errmsg, msg, arg );
  682.     pinpoint_message( errmsg );
  683.     }
  684.  
  685.  
  686. /* pinpoint_message - write out a message, pinpointing its location */
  687.  
  688. void pinpoint_message( str )
  689. char str[];
  690.  
  691.     {
  692.     fprintf( stderr, "\"%s\", line %d: %s\n", infilename, linenum, str );
  693.     }
  694.  
  695.  
  696. /* yyerror - eat up an error message from the parser;
  697.  *         currently, messages are ignore
  698.  */
  699.  
  700. void yyerror( msg )
  701. char msg[];
  702.  
  703.     {
  704.     }
  705.